package com.tgy.排序;

import java.util.Arrays;

/***
 * @ClassName: QuickSort
 * @Description: 快速排序
 * @Auther: tanggy3
 * @Date: 17:26 2022/8/24
 * @version : V1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        //int[] arr = {-9,78,0,23,-567,70, -1,900, 4561};
        int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
        int[] intArr = Utils.getIntArr(80000000);
        int[] intArr1 = Utils.getIntArr(8);

        //quickSort(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));
//        long l = System.currentTimeMillis();
//        quickSort(intArr, 0, intArr.length - 1);//13ms，八千万需要10s
//        System.out.println("耗时" + (System.currentTimeMillis() - l) + "ms");
//        ShellSort.shellSortMove(intArr1);//八千万需要41s
//        System.out.println(Arrays.toString(arr));


        int[] intArr2 = Utils.getIntArr(8000000);
        long l1 = System.currentTimeMillis();
        quickSort(intArr2, 0, intArr2.length - 1);
        System.out.println("耗时" + (System.currentTimeMillis() - l1) + "ms");


        int[] intArr3 = Utils.getIntArr(8000000);
        long l2 = System.currentTimeMillis();
        quickSortFirst(intArr3, 0, intArr3.length - 1);
        System.out.println("耗时" + (System.currentTimeMillis() - l2) + "ms");
        //System.out.println(Arrays.toString(intArr3));


    }

    /**
     * 快速排序中间数为基准
     *
     * @param arr
     * @param left  左下标
     * @param right 右下标
     * @return
     */
    public static int[] quickSort(int[] arr, int left, int right) {
        int temp = 0; //临时变量，作为交换时使用
        int l = left;//左下标
        int r = right;//右下标
        int pivot = arr[(left + right) / 2];//基准值
        /**
         * while 循环得目的是为了让比基准数值小得放在mid左边，大的放右边
         */
        while (l < r) {
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while (arr[l] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while (arr[r] > pivot) {
                r -= 1;
            }
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是小于等于pivot值，右边全部是大于等于pivot值
            if (l >= r) {
                break;
            }

            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
            if (arr[l] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
            if (arr[r] == pivot) {
                l += 1;
            }
        }


        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
        return arr;
    }

    /**
     * 快速排序首位数为基准
     * 从右边找小的数放到前一个坑里，从左边找大于基数的数放到坑里
     * 每一个被保存了值的数都是一个坑洞
     * 这个更快
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static void quickSortFirst(int[] arr, int left, int right) {
        if (left < right) {
            //swap(arr,left, (left + right) / 2); //将中间的这个数和第一个数交换
            int l = left, r = right, x = arr[left];
            while (l < r) {
                while (l < r && arr[r] >= x) // 从右向左找第一个小于x的数
                {
                    r--;
                }
                if (l < r) {
                    arr[l] = arr[r];
                    l++;
                }
                while (l < r && arr[l] < x) // 从左向右找第一个大于等于x的数
                {
                    l++;
                }
                if (l < r) {
                    arr[r] = arr[l];
                    r--;
                }
            }//外层while完结
            /**
             * 这时候l = r
             * 0-4,6-9再分别计算就可以了
             * 因为l的位置已经确定不用再调整了
             */
            arr[l] = x;
            quickSortFirst(arr, left, r - 1);
            quickSortFirst(arr, l + 1, right);

        }
    }

    public static void swap(int[] arr, int l, int r) {
        int i = arr[l];
        arr[l] = arr[r];
        arr[r] = i;
    }


    /**
     * 挖坑
     *
     * @param s
     * @param l
     * @param r
     * @return
     */
    int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
    {
        int i = l, j = r;
        int x = s[l]; //s[l]即s[i]就是第一个坑
        while (i < j) {
            // 从右向左找小于x的数来填s[i]
            while (i < j && s[j] >= x)
                j--;
            if (i < j) {
                s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
                i++;
            }

            // 从左向右找大于或等于x的数来填s[j]
            while (i < j && s[i] < x)
                i++;
            if (i < j) {
                s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
                j--;
            }
        }
        //退出时，i等于j。将x填到这个坑中。
        s[i] = x;

        return i;
    }

    /**
     * 分治算法
     *
     * @param s
     * @param l
     * @param r
     */
    void quick_sort1(int s[], int l, int r) {
        if (l < r) {
            int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
            quick_sort1(s, l, i - 1); // 递归调用
            quick_sort1(s, i + 1, r);
        }
    }


    private static int get_mid(int arr[], int left, int right) {
        int pivot = arr[left];//自定义排序中心轴，这里把arr[left]存到pivot中去，此时arr[left]为空。pivot相当于一个中间量
        while (left < right) {//当left与right指针相遇的时候退出循环，双指针遍历结束
            /**
             * right指针从右往左遍历，当arr[right]>=pivot，
             * 即满足以pivot为中轴，小放左，大放右的条件时，right指针继续往右遍历。
             * 当arr[right]<pivot的时候，把当前值arr[right]赋给空置arr[left]，此时arr[right]成了空值。
             */
            while (arr[right] >= pivot && left < right) right--;
            arr[left] = arr[right];
            /**
             * 到left指针从左往右遍历，当arr[left]<=pivot，
             * 即满足以pivot为中轴，小放左，大放右的条件时，left指针继续往左遍历。
             * 当arr[left]>pivot的时候，把当前值arr[left]赋给空置arr[right]，此时arr[left]成了空值。
             */
            while (arr[left] <= pivot && left < right) left++;
            arr[right] = arr[left];
        }
        //经历了上面的循环实现了pivot为中轴，小放左，大放右的格局
        arr[left] = pivot;//最后把存放在pivot值放回数组空arr[left]中
        return left;//返回中轴所在的下标位置。
    }


    private static void quick_sort(int[] arr, int left, int right) {
        if (left < right) {
            /*将arr[left..right]均分为两部分arr[left..mid]和arr[mid+1..right]
             * ,以pivot为中轴，小放左，大放右。这是第一步。*/
            int mid = get_mid(arr, left, right);//接收中轴所在的下标位置。
            quick_sort(arr, left, mid - 1);//递归地对arr[left..mid]进行快速排序，使得左子序列有序
            quick_sort(arr, mid + 1, right);//递归地对arr[mid+1..right]进行快速排序，使得左子序列有序
        }
    }


    //快速排序
    static void quick_sort2(int s[], int l, int r) {
        if (l < r) {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j) {
                while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
                    j--;
                if (i < j)
                    s[i++] = s[j];

                while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                    i++;
                if (i < j)
                    s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用
            quick_sort(s, i + 1, r);
        }
    }
}
